| 1. Identificação | ||||||||||
| Tipo de Referência | Tese ou Dissertação (Thesis) | |||||||||
| Site | mtc-m21c.sid.inpe.br | |||||||||
| Código do Detentor | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S | |||||||||
| Identificador | 8JMKD3MGP3W34R/3TQ87S5 | |||||||||
| Repositório | sid.inpe.br/mtc-m21c/2019/08.07.15.41 | |||||||||
| Última Atualização | 2019:11.11.10.28.05 (UTC) simone | |||||||||
| Repositório de Metadados | sid.inpe.br/mtc-m21c/2019/08.07.15.41.39 | |||||||||
| Última Atualização dos Metadados | 2019:11.11.21.53.17 (UTC) administrator | |||||||||
| Chave Secundária | INPE-18235-TDI/2918 | |||||||||
| Chave de Citação | Véras:2019:EsPrAm | |||||||||
| Título | Estudo de processos de amostragem não uniforme/informada em árvores aleatórias de exploração rápida visando o planejamento automático de rotas para veículos aéreos não tripulados  | |||||||||
| Título Alternativo | Study of non-uniform/informed sampling processes in rapidly-exploring random trees for the automatic path planning for unmanned aerial vehicles | |||||||||
| Curso | CAP-COMP-SESPG-INPE-MCTIC-GOV-BR | |||||||||
| Ano | 2019 | |||||||||
| Data | 2019-08-09 | |||||||||
| Data de Acesso | 05 maio 2024 | |||||||||
| Tipo da Tese | Tese (Doutorado em Computação Aplicada) | |||||||||
| Tipo Secundário | TDI | |||||||||
| Número de Páginas | 237 | |||||||||
| Número de Arquivos | 1 | |||||||||
| Tamanho | 33010 KiB | |||||||||
| 2. Contextualização | ||||||||||
| Autor | Véras, Luiz Gustavo Diniz de Oliveira | |||||||||
| Banca | Körting, Thales Sehn (presidente) Guimarães, Lamartine Nogueira Frutuoso (orientador) Medeiros, Felipe Leonardo Lôbo (orientador) Carvalho, Solon Venâncio de Pinto, Maria José Pillat, Valdir Gil | |||||||||
| Endereço de e-Mail | luiizgustavo@gmail.com | |||||||||
| Universidade | Instituto Nacional de Pesquisas Espaciais (INPE) | |||||||||
| Cidade | São José dos Campos | |||||||||
| Histórico (UTC) | 2019-08-07 15:43:50 :: luiizgustavo@gmail.com -> pubtc@inpe.br :: 2019-08-14 12:56:26 :: pubtc@inpe.br -> luiizgustavo@gmail.com :: 2019-09-22 21:57:19 :: luiizgustavo@gmail.com -> pubtc@inpe.br :: 2019-09-24 17:16:13 :: pubtc@inpe.br -> luiizgustavo@gmail.com :: 2019-09-25 06:12:03 :: luiizgustavo@gmail.com -> pubtc@inpe.br :: 2019-10-31 15:50:23 :: pubtc@inpe.br -> administrator :: 2019-11-06 11:16:45 :: administrator -> simone :: 2019-11-11 13:14:15 :: simone :: -> 2019 2019-11-11 13:15:51 :: simone -> administrator :: 2019 2019-11-11 13:19:09 :: administrator -> pubtc@inpe.br :: 2019 2019-11-11 13:19:44 :: pubtc@inpe.br -> simone :: 2019 2019-11-11 13:20:08 :: simone -> administrator :: 2019 2019-11-11 21:53:17 :: administrator -> :: 2019 | |||||||||
| 3. Conteúdo e estrutura | ||||||||||
| É a matriz ou uma cópia? | é a matriz | |||||||||
| Estágio do Conteúdo | concluido | |||||||||
| Transferível | 1 | |||||||||
| Palavras-Chave | planejamento de rota RRT grades de Sukharev vértices convexos amostragem não uniforme/informada path planning RRT Sukharev grids convex vertices non uniform/informed sampling | |||||||||
| Resumo | A etapa de planejamento de rota na navegação de um Veículo Aéreo Não Tripulado (VANT) garante que uma rota cinematicamente e dinamicamente viável e sem colisão seja planejada entre um ponto inicial e um ponto final em um ambiente de navegação. Um dos algoritmos mais utilizados nessa etapa é o Árvore Aleatória de Exploração Rápida (RRT, do inglês Rapidly-exploring Random Tree), o qual constrói iterativamente uma estrutura de dados em árvore onde cada um de seus nós é coletado aleatoriamente como uma amostra do ambiente de navegação até que os pontos de navegação inicial e final sejam conectados através deles. O algoritmo RRT* (lê-se RRT estrela) é uma variação do algoritmo RRT que garante o planejamento da rota com o menor comprimento para o VANT baseado em realocação de arestas de nós vizinhos, porém, devido a essa nova operação, exige um alto custo computacional. Alguns autores afirmam que ao direcionar a coleta de novas amostras para regiões específicas no ambiente de navegação, seria possível melhorar o tempo de planejamento desse algoritmo. Processos que utilizam esse tipo de abordagem são conhecidos como amostragem não uniforme/informada. Nesta tese, é apresentado um estudo do uso de dois processos de amostragem não uniforme/informada no algoritmo RRT*, um baseado em grade de Sukharev (um tipo de grade que gera amostras com dispersão ótima) e outro nos vértices convexos das envoltórias de segurança dos obstáculos. A influência de cada um dos processos considerados no tempo de planejamento e comprimento das rotas planejadas pelo algoritmo RRT* é estudada. Com base nessas verificações, é apresentado um novo algoritmo baseado no RRT*, denominado RRT* Sukharev Vértices (RRT*-SV), no qual são utilizados ambos os processos estudados neste trabalho. Testes computacionais foram realizados para verificar se o algoritmo RRT*-SV apresenta menor tempo de planejamento do que o algoritmo RRT* e outros algoritmos da literatura como, por exemplo, os algoritmos RRT*-Smart, o Informed-RRT* e o BIT* (do inglês Batch Informed Trees Star), que também utilizam processos de amostragem não uniforme/informada. Os testes computacionais foram realizados considerando diversos ambientes de navegação com representação contínua e bidimensional e com diferentes quantidades e distribuições espaciais de obstáculos estáticos poligonais. Os resultados indicam que o processo de amostragem proposto acelera o tempo de planejamento do RRT* e demonstram que o algoritmo RRT*-SV possui melhor desempenho em vários tipos de ambientes de navegação quando comparado aos outros algoritmos considerados. Pelo desempenho demonstrado, o algoritmo RRT*-SV se mostra adequado para uso em aplicações de navegação em tempo real de VANTs que tenham como restrição o planejamento da rota de menor comprimento. ABSTRACT: The path planning step in the navigation of an Unmanned Aerial Vehicle (UAV) ensures that a kinodynamically viable, collision-free path between a start point and an end point in a navigation environment can be planned. One of the most commonly used algorithms for path planning is the Rapidly-exploring Random Tree (RRT), which iteratively constructs a tree data structure where each of its nodes is randomly collected as a sample of the navigation environment until the start and end navigation points are connected through them. The RRT* algorithm (read RRT star) is a variation of the RRT algorithm that ensures the planning of the path with the shortest length for the UAV based on edge relocation of neighboring node edges. However, due to this new operation requires, it require a high computational cost. Some authors affirm that by biasing the collection of new samples to specific regions in the navigation environment, it would be possible to improve the planning time of this algorithm. Processes using this type of approach are known as non-uniform/informed sampling. In this thesis, a study of the use of two non-uniform/informed sampling processes in the RRT* algorithm, one based on Sukharev grid (one type of grid that generates optimally dispersed samples) and the other on the convex vertices of safety envelopes of the obstacles, is carried out together with the RRT* algorithm. The influence of each of the considered processes on the planning time and length of the path planned by the RRT* algorithm is studied. Based on these verifications, a new RRT* based algorithm called RRT* Sukharev Vertices (RRT*-SV) is presented, in which both processes studied in this work are used. Computational tests were performed to verify if the RRT*-SV algorithm has shorter planning time than the RRT* algorithm and other literature algorithms such as RRT*-Smart, Informed-RRT* and BIT* (Batch Informed Trees Star) algorithms, which also uses non-uniform/informed sampling processes. The computational tests were performed considering several navigation environments with continuous and two-dimensional representation and with different quantities and spatial distributions of polygonal static obstacles. The results indicate that the proposed sampling process accelerates the RRT* planning time and shows that the RRT*-SV algorithm has better performance in various types of navigation environments when compared to the other algorithms considered. Due to its performance, the RRT*-SV algorithm is suitable for use in real-time UAV navigation applications that have as constraint the planning of the path with the shortest length. | |||||||||
| Área | COMP | |||||||||
| Arranjo | urlib.net > BDMCI > Fonds > Produção pgr ATUAIS > CAP > Estudo de processos... | |||||||||
| Conteúdo da Pasta doc | acessar | |||||||||
| Conteúdo da Pasta source |
| |||||||||
| Conteúdo da Pasta agreement |
| |||||||||
| 4. Condições de acesso e uso | ||||||||||
| URL dos dados | http://urlib.net/ibi/8JMKD3MGP3W34R/3TQ87S5 | |||||||||
| URL dos dados zipados | http://urlib.net/zip/8JMKD3MGP3W34R/3TQ87S5 | |||||||||
| Idioma | pt | |||||||||
| Arquivo Alvo | publicacao.pdf | |||||||||
| Grupo de Usuários | gabinete@inpe.br luiizgustavo@gmail.com pubtc@inpe.br simone | |||||||||
| Visibilidade | shown | |||||||||
| Licença de Direitos Autorais | urlib.net/www/2012/11.12.14.48 | |||||||||
| Detentor dos Direitos | originalauthor yes | |||||||||
| Permissão de Leitura | allow from all | |||||||||
| Permissão de Atualização | não transferida | |||||||||
| 5. Fontes relacionadas | ||||||||||
| Repositório Espelho | urlib.net/www/2017/11.22.19.04.03 | |||||||||
| Unidades Imediatamente Superiores | 8JMKD3MGPCW/3F2PHGS | |||||||||
| Acervo Hospedeiro | urlib.net/www/2017/11.22.19.04 | |||||||||
| 6. Notas | ||||||||||
| Campos Vazios | academicdepartment affiliation archivingpolicy archivist callnumber contenttype copyholder creatorhistory descriptionlevel dissemination doi electronicmailaddress format group isbn issn label lineage mark nextedition notes number orcid parameterlist parentrepositories previousedition previouslowerunit progress readergroup resumeid schedulinginformation secondarydate secondarymark session shorttitle sponsor subject tertiarymark tertiarytype url versiontype | |||||||||